/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 * 基数排序/桶排序
 * </p>
 * @author LvJing
 * @version $Id:RadixSort.java v1.0 2018/7/22 上午10:16 LvJing Exp $
 */
public class RadixSort {

    /*
    基本思想：这种排序算法比较特殊，属于分配排序，这里不说太生僻的概念，通俗点说就是，对于一个数组序列，先比较每个数的个位，把相同个位数放在一个
    数组里，然后取出，这时这个数组就在个数上是有序的（要保证放入和取出数组的顺序一致）；第二趟把十位数相同的放在一个数组里，再取出，这时就会在个
    位的基础上对于十位数又是有序的，如果这些数均小于100，那么就排序完毕，取出的数已经是有序的，如果还有大于100的数，就可以继续排序，直到没有更高
    的位数。
    注意：从上面描述它的算法实现的过程，已经可以看出这种算法是不支持正负数同时排序的，因为它并没有对数进行比较，只是对数的位数进行比较。
     */

    public void radixSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }

        // 找出最大数，知道排序的趟数
        int max = arr[0];
        for (int num : arr) {
            if (max < num) {
                max = num;
            }
        }

        System.out.println(Arrays.toString(arr));
        System.out.println("Max Number:" + max);

        int radix = 1;// 排序位数 1  10  100
        int length = arr.length;
        int[][] bucket = new int[10][length];// 这里设置二维数组长度为length的原因为，防止出现某一位上的数都相同，所有数落在一个数组里
        int[] order = new int[length];// 记录桶的元素个数
        while (radix < max) {

            // 把某一位相同的数依次放入桶中
            for (int num : arr) {
                int digit = (num / radix) % 10;
                bucket[digit][order[digit]] = num;
                order[digit]++;// 桶里位置后移
            }

            // 把桶中的元素再放回原数组
            int pos = 0;
            for (int i = 0; i < 10; i++) {
                // 桶里没有元素
                if (order[i] == 0) {
                    continue;
                }

                for (int j = 0; j < order[i]; j++) {
                    arr[pos++] = bucket[i][j];
                }

                order[i] = 0;// 桶元素清零
            }

            radix *= 10;
            System.out.println(Arrays.toString(arr));
        }
    }

    @Test
    public void test() {
        int[] arr = new int[20];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(1000);
        }
        radixSort(arr);
    }
}
